package com.wuyou.simple;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @Description 2824. 统计和小于目标的下标对数目
 * @Author yh.zhang
 * @Date 2023/11/24 9:06
 */
public class CountPairs {


    public static void main(String[] args) {
        Integer[] nums = {-5, 0, -7, -1, 9, 8, -9,};
        int target = -14;
        System.out.println(solution_2(Arrays.asList(nums), target));
    }

    public static int solution_2(List<Integer> nums, int target) {
        Collections.sort(nums);
        int ans = 0;
        int n = nums.size();

        for (int i = 0; i < n; i++) {
            int numI = nums.get(i);
            int left = i + 1, right = n, mid = 0;
            if (numI + nums.get(n - 1) < target) {
                ans += n - 1 - i;
            } else if (i < n - 1 && numI + nums.get(i + 1) >= target) {
                continue;
            } else {
                while (left < n && left <= right) {
                    mid = ((right - left) / 2) + left;
                    int numJ = nums.get(mid);
                    if (numI + numJ < target) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                ans += Math.max(left - i - 1, 0);
            }
        }
        return ans;
    }


    public static int solution_1(List<Integer> nums, int target) {
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                int temp = nums.get(i) + nums.get(j);
                if (temp < target) {
                    ans++;
                }
            }
        }
        return ans;
    }

}
